package com.my.algorithmlearning.leetcode;

import java.util.Arrays;

/**
 * @ClassName Medium_240_SearchSortedMatrix
 * @Description Medium_240_SearchSortedMatrix
 * @Author wanghaiwei
 * @Date 2023/7/14 11:30
 */
public class Medium_240_SearchSortedMatrix {
    public boolean searchMatrix_V1_NormalBinarySearchPerRow(int[][] matrix, int target) {
        if (matrix == null || matrix.length <= 0) {
            return false;
        }
        //特判1：只有一行
        if (matrix.length == 1) {
            return Arrays.binarySearch(matrix[0], target) >= 0;
        }
        //特判2：只有一列
        if (matrix[0].length == 1) {
            for (int i = 0; i < matrix.length; i++) {
                if (target == matrix[i][0]) {
                    return true;
                }
            }
            return false;
        }
        //每行使用二分法查找
        for (int i = 0; i < matrix.length; i++) {
            if (target >= matrix[i][0] && target <= matrix[i][matrix[i].length - 1]) {
                if (Arrays.binarySearch(matrix[i], target) >= 0) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix_V2_FromRightCorner_BinarySearch(int[][] matrix, int target) {
        if (matrix == null || matrix.length <= 0) {
            return false;
        }
        //特判1：只有一行
        if (matrix.length == 1) {
            return Arrays.binarySearch(matrix[0], target) >= 0;
        }
        //特判2：只有一列
        if (matrix[0].length == 1) {
            for (int i = 0; i < matrix.length; i++) {
                if (target == matrix[i][0]) {
                    return true;
                }
            }
            return false;
        }
        //从右上角开始查找
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            //如果当前值比目标值大，那么当前列的所有值都比目标值大，所以列数减1，舍弃该列
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                //如果当前值比目标值小，那么当前行的所有值都比目标值小，所以行数加一，舍弃该行
                row++;
            } else {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Medium_240_SearchSortedMatrix searchSortedMatrix = new Medium_240_SearchSortedMatrix();
        int[][] input = new int[][]{{1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};
        System.out.println("解法一：使用二分法查找：" + searchSortedMatrix.searchMatrix_V1_NormalBinarySearchPerRow(input, 5));
        System.out.println("解法二：从右上角开始搜索，变形二分法" + searchSortedMatrix.searchMatrix_V2_FromRightCorner_BinarySearch(input, 5));

        input = new int[][]{{1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};
        System.out.println("解法一：使用二分法查找：" + searchSortedMatrix.searchMatrix_V1_NormalBinarySearchPerRow(input, 20));
        System.out.println("解法二：从右上角开始搜索，变形二分法" + searchSortedMatrix.searchMatrix_V2_FromRightCorner_BinarySearch(input, 20));
    }
}
